/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sirtet.tetris.generator;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 *
 * @author yunglu
 */
public class Partition {

    private static List<Integer> copyList(List<Integer> src) {
        List<Integer> destList = new ArrayList<Integer>();
        Iterator iter = src.iterator();
        while (iter.hasNext()) {
            Integer i = (Integer) iter.next();
            destList.add(i);
        }
        return destList;
    }

    private static void partitionInt(int n, List<Integer> pList,
            List<List<Integer>> allList) {
        if (n == 0) {
            // We must make a copy of pList.
            // Java does not make a copy. If we use allList.add(pList);
            // and change pList later, the element in allList is also changed            
            allList.add(copyList(pList));
            if (pList.size() >= 2) {
                pList.remove(pList.size() - 1);
                pList.remove(pList.size() - 1);
            }
        }
        for (int i = 1; i <= n; i++) {
            pList.add(new Integer(i));
            partitionInt(n - i, pList, allList);
        }
    }

    public static List<List<Integer>> partition(int n) {
        List<Integer> pList = new ArrayList<Integer>();
        // one partition
        List<List<Integer>> allList = new ArrayList<List<Integer>>();
        // all partitions
        partitionInt(n, pList, allList);
        return allList;
    }
}
